package com.lsa.letcode.the86.partitionList;

import com.lsa.letcode.common.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
    	ListNode n = head;
    	
    	ListNode startLt = null; // start (first node) of the LT (<) area
    	ListNode endLt = null;   // end (last node) of the LT area
    	ListNode startGte = null; // start (first node) of the GTE (>=) area
    	ListNode endGte = null;   // end (last node) of the GTE area
    	
    	while(n != null) {
    		if (n.val < x) {
    			if (startLt != null) {
    				endLt.next = n;
    			}
    			else {
    				startLt = n;
    			}
    			endLt = n;
    		}
    		else {
    			if (startGte != null) {
    				endGte.next = n;
    			}
    			else {
    				startGte = n;
    			}
    			endGte = n;
    		}
    		n = n.next;
    	}

    	if (startLt != null && startGte != null ) {
    		endLt.next = startGte;
    		endGte.next = null;
    		head = startLt;
    	}
    	
    	return head;
    }
}